/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lenovo
 * Date: 2025-06-24
 * Time: 23:50
 */
//力扣：https://leetcode.cn/problems/merge-two-sorted-lists/
    //将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    public void print(ListNode list){
        while(list!=null){
            System.out.print(list.val+" ");
            list=list.next;
        }
    }
 }
public class Test {
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }
        ListNode head=new ListNode();
        ListNode last=head;
        while(list1!=null&&list2!=null){
            if(list1.val<=list2.val){
                last.next=list1;
                last=list1;
                list1=list1.next;
            }
            else{
                last.next=list2;
                last=list2;
                list2=list2.next;
            }
        }
        if(list1==null){
            last.next=list2;
        }
        else{
            last.next=list1;
        }
        return head.next;
    }
    public static void main(String[] args) {
        ListNode list1=new ListNode(1);
        ListNode list2=new ListNode(2);
        ListNode list3=new ListNode(3);
        ListNode list4=new ListNode(4);
        ListNode list5=new ListNode(5);
        ListNode list6=new ListNode(6);
        list1.next=list3;
        list3.next=list5;
        list2.next=list4;
        list4.next=list6;
        ListNode list=mergeTwoLists(list1,list2);
        list.print(list);

    }
}
